/**
 * 
 */
package solution.tree.bfs;

import java.util.ArrayList;
import java.util.List;

import lib.tree.BNode;
import lib.tree.TreeUtil;

import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 * 
 */
public class BFSLink {

	List<BNode> getBFSLink(BNode tree) {
		if (tree == null)
			return null;

		List<BNode> levelHead = new ArrayList<BNode>();

		// handle the first line (root)
		BNode qHead = tree, qTail = tree;
		int count = 1;
		int qSize = 1;
		levelHead.add(qHead);

		while (qHead != null) {
			// enqueue before dequeue.
			// otherwise, the enqueue operation will be more complex.
			if (qHead.left != null) {
				qTail.next = qHead.left; // enqueue
				qTail = qTail.next;
				qSize++;
			}

			if (qHead.right != null) {
				qTail.next = qHead.right;
				qTail = qTail.next;
				qSize++;
			}

			count--;
			if (count == 0) {
				// end of one line
				BNode tmp = qHead;
				qHead = qHead.next;
				if (qHead == null)
					return levelHead;
				qSize--;
				tmp.next = null;

				// start of another line
				count = qSize;
				levelHead.add(qHead);
			} else {
				qHead = qHead.next;
				qSize--;
			}
		}
		return levelHead;
	}

	@Test
	public void test() {
		BNode tree = new TreeUtil().makeTree("4(2(1,3),6(5,7)))");

		List<BNode> levelHead = getBFSLink(tree);

		for (BNode node : levelHead) {
			BNode rNode = node;
			do {
				System.out.print(rNode.value);
				rNode = rNode.next;
			} while (rNode != null);
			System.out.println();
		}
	}
}
